#include<iostream>
#include<string>
#include<vector>
#include<stack>
using namespace std;

class Solution {
public:
    bool isValid(string s) {
        stack<char> V;
        for(int i=0;i<s.size();i++){
            if(s[i]=='('||s[i]=='{'||s[i]=='['){
                V.push(s[i]);
            }
            else{
                if(s[i]==')'){
                    if(!V.empty()&&V.top()=='('){
                        V.pop();
                    }
                    else{
                        return false;
                    }
                }
                else if(s[i]==']'){
                    if(!V.empty()&&V.top()=='['){
                        V.pop();
                    }
                    else{
                        return false;
                    }
                }
                else{
                    if(!V.empty()&&V.top()=='{'){
                        V.pop();
                    }
                    else{
                        return false;
                    }
                }
            }

        }
        if(V.empty()){
            return true;
        }
        else{
            return false;
        }
    }
};

int main(){
    Solution S;
    cout<<S.isValid("{[]}")<<endl;
}
